package graph;

import java.util.Arrays;

class Prim {

	public int doPrim(int n, int[][] map) {
		boolean[] visit = new boolean[n];
		int[] d = new int[n];
		Arrays.fill(d, Integer.MAX_VALUE);
		Arrays.fill(visit, false);
		int u = 0;
		d[0] = Integer.MAX_VALUE;
		visit[0] = true;
		for (int i = 1; i < n; ++i) {
			int w = 0;
			for (int v = 1; v < n; v++) {
				if (!visit[v]) {
					if (map[u][v] < d[v])
						d[v] = map[u][v];
					if (d[v] < d[w])
						w = v;
				}
			}
			u = w;
			visit[u] = true;
		}
		int min = 0;
		for (int i = 1; i < n; i++)
			min += d[i];
		return min;
	}

}
